package leetcode.pre50;

/**
 * 最长回文子串
 *
 * @date 2020/3/23 17:17
 */
public class Code05_LongestPalindrome {
    //方式1：最所有子串进行判断是否是回文串。o(N³)复杂度。
    public static String longestPalindrome(String s) {
        if (s == null || s.length() == 0) return s;
        int max = 1;
        String res = s.substring(0, 1);
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                if (isPalindrome(s, i, j)) {
                    if (j - i + 1 > max) {
                        max = j - i + 1;
                        res = s.substring(i, j + 1);
                    }
                }
            }
        }
        return res;
    }

    private static boolean isPalindrome(String s, int i, int j) {
        while (i < j) {
            if (s.charAt(i) == s.charAt(j)) {
                i++;
                j--;
            } else {
                return false;
            }
        }
        return true;
    }

    //方式2：遍历字符串，遍历过程中对每个位置进行判断，往外扩
    public static String longestPalindrome1(String s) {
        if (s == null || s.length() == 0) return s;

        int start = 0;
        int end = 0;
        String res = s.substring(0, 1);
        for (int i = 0; i < s.length(); i++) {
            //对当前位置进行奇偶回文判断
            int len1 = expand(s, i, i);
            int len2 = expand(s, i, i + 1);
            int len = Math.max(len1, len2);
            //如果是奇回文，那么对于位置i往前往后都是len/2 = len-1/2。
            //如果是偶回文，那么对于位置i往前是(len-1)/2，往后是len/2
            //所以说往前是len-1/2，往后是len/2
            if (len > end - start + 1) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
                res = s.substring(start, end + 1);
            }
        }
        return res;

    }

    //方式3：对字符串处理，统一处理为奇数个。
    public static String longestPalindrome2(String s) {
        if (s == null || s.length() == 0) return s;
        s = getModify(s);
        int start = 0;
        int end = 0;
        String res = s.substring(0, 1);
        for (int i = 0; i < s.length(); i++) {
            //奇回文即可。 1被修饰为#1#，   11被修饰为#1#1#。都是奇回文。
            int len = expand(s, i, i);
            if (len > end - start + 1) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
                res = s.substring(start, end + 1);
            }
        }
        return res.replace("#", "");

    }

    private static String getModify(String s) {
        StringBuffer sb = new StringBuffer("#");
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i)).append("#");
        }
        return sb.toString();
    }

    private static int expand(String s, int i, int j) {
        while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            i--;
            j++;
        }
        //i+1,j-1;
        i++;
        j--;
        return j - i + 1;
    }

    /**
     * Manacher算法
     *
     * @param s
     */
    public static String longestPalindrome3(String s) {
        if (s == null || s.length() == 0) return s;
        s = getModify(s);
        //回文边界
        int R = -1;
        //回文边界对应的中心
        int centerR = -1;
        //最大回文长度
        int max = 0;
        //最大回文长度对应的回文中心
        int centerMax = -1;

        //每个位置的回文半径
        int[] p = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            //情况2的 case1 和 case2
            if (i < R) {
                p[i] = Math.min(p[2 * centerR - i], R - i + 1);
            } else {
                p[i] = 1;
            }
            //往外扩，情况1和情况2的case3
            while (i - p[i] >= 0 && i + p[i] < s.length()) {
                if (s.charAt(i - p[i]) == s.charAt(i + p[i])) {
                    p[i]++;
                } else {
                    break;
                }
            }
            //更新回文边界和中心
            if (i + p[i] - 1 > R) {
                centerR = i;
                R = i + p[i] - 1;
            }
            //更新最大回文中心和长度
            if (p[i] > max) {
                max = p[i];
                centerMax = i;
            }
        }
        //当前回文中心是centerMax，回文半径是max
        //回文起点是 centerMax - (max-1)
        //回文终点是 centerMax + (max-1)
        return s.substring(centerMax - max + 1, centerMax + max)
                .replace("#", "");
    }

    public static void main(String[] args) {
//        System.out.println(longestPalindrome("bb"));
//        System.out.println(longestPalindrome("a"));
//        System.out.println(longestPalindrome("1bb2"));
        System.out.println(longestPalindrome3("babad"));
    }
}
